package list

func isPalindrome(head *ListNode) bool {

	firstHalf := head
	secondHalf := getSecondHalf(head)
	secondHalf = reverse(secondHalf)

	temp1, temp2 := firstHalf, secondHalf
	for temp1 != nil && temp2 != nil {
		if temp1.Val != temp2.Val {
			return false
		}
		temp1 = temp1.Next
		temp2 = temp2.Next
	}

	return true

}

// 反转
func reverse(head *ListNode) *ListNode {

	var temp *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = temp
		temp = cur
		cur = next
	}
	return temp
}

// 找后半段
func getSecondHalf(head *ListNode) *ListNode {
	slow, fast := head, head

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	return slow
}
